1355E - Restorer Distance - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
// tree_order_statistics_node_update> ordered_set;
#define int long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define rz resize
#define ii pair<int, int>
#define vii vector<pair<int,int>>
#define vv vector<vector<int>>
#define vv vector<vector<int>>
#define vi vector<int>
#define endl "\n"
#define pb push_back
#define be begin
#define up upper_bound
#define lo lower_bound
#define bi binary_search
#define si set<int>
#define msi multiset<int>
#define mii map<int, int>
#define all(v) v.begin(), v.end()
#define mems1(a) memset(a, -1, sizeof(a))
#define mems0(a) memset(a, 0, sizeof(a))
#define rep(i, s, e) for (int i = s; i < e; i++)
#define rrep(i, s, e) for (int i = s - 1; i >= e; i--)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pr cout<<"a"<<endl
int n,a,r,m;
vi h;
int f(int x){
    int c1=0,c2=0;
    rep(i,0,n){
        if(h[i]>x)c1+=(h[i]-x);
        else c2+=x-h[i];
        
    }
    int ans=0;
    if(c1>c2){
        ans+=(c2*(min(r+a,m))+(c1-c2)*r);
    }
    else{
        ans+=(c1*(min(r+a,m))+(c2-c1)*a);
    }
    return ans;
}
void solve(){
    cin>>n>>a>>r>>m;
    h.rz(n);
    int lo=0,hi=0;
    rep(i,0,n){
        cin>>h[i];
        hi=max(hi,h[i]);
    }
    while(lo<=hi){
        int m1=lo+(hi-lo)/3,m2=hi-(hi-lo)/3;
        if(f(m1)>f(m2)){
            lo=m1+1;
        }
        else{
            hi=m2-1;
        }
    }
    cout<<min(f(lo),f(hi))<<endl;
    

    
}  
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin >> t;
    for (int i = 0; i < t; i++)
    {
        solve();
    }
}